/**
 * [20] 有效的括号
 *
 * @format
 * @lc app=leetcode.cn id=20 lang=javascript
 */

// @lc code=start
/**
 * @param {string} s
 * @return {boolean}
 */
// 栈优化
// 左括号入栈，右括号比对（匹配则出栈）
var isValid = function (s) {
    const stack = [s[0]]
    const map = { ")": "(", "]": "[", "}": "{" }
    if (s.length % 2 != 0) return false
    for (c of s.slice(1)) {
        let top = stack.length - 1
        // console.log(c, top, stack)
        if (map[c] == undefined) stack.push(c)
        else if (map[c] == stack[top]) stack.pop()
        else return false
    }
    return stack.length == 0
}
/* // 栈
var isValid = function (s) {
    const stack = []
    // function isMatched(s1, s2) {
    //     if (s1 == "(" && s2 == ")") return true
    //     else if (s1 == "[" && s2 == "]") return true
    //     else if (s1 == "{" && s2 == "}") return true
    //     else return false
    // }
    const brackets = { "(": ")", "[": "]", "{": "}" }
    for (char of s) {
        let top = stack.length - 1
        // if (isMatched(stack[top], s[i])) stack.pop()
        if (brackets[stack[top]] == char) stack.pop()
        else stack.push(char)
    }
    return stack.length == 0
} */
// Accepted
// 97/97 cases passed (65 ms)
// Your runtime beats 49.17 % of javascript submissions
// Your memory usage beats 47.57 % of javascript submissions (49.6 MB)
// Accepted
// 97/97 cases passed (59 ms)
// Your runtime beats 82.25 % of javascript submissions
// Your memory usage beats 31.38 % of javascript submissions (50.3 MB)
// debugger
// const s = "()[]{}"
// const result = isValid(s)
// console.log(result)
// @lc code=end
